package leetcode.每日一题;

import org.junit.Test;

/**
 * @author ：zsy
 * @date ：Created 2022/9/23 2:50 PM
 * @description：https://leetcode.cn/problems/design-linked-list/
 */
public class 设计链表 {

    @Test
    public void test() {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addAtHead(100);
        myLinkedList.addAtTail(200);
        myLinkedList.addAtTail(300);
        myLinkedList.addAtTail(400);
        myLinkedList.addAtTail(500);
        myLinkedList.addAtIndex(3, 350);
        myLinkedList.addAtIndex(6, 600);
        myLinkedList.deleteAtIndex(3);
        myLinkedList.head.list();
    }

    class MyLinkedList {

        Node head;
        Node tail;

        public MyLinkedList() {
            head = new Node(-1);
        }

        public int get(int index) {
            Node node = getNodeByIdxFromHead(index);
            return node == null ? -1 : node.val;
        }

        public void addAtHead(int val) {
            Node node = new Node(val);
            Node next = head.next;
            head.next = node;
            node.next = next;
            if (tail == null) {
                tail = node;
            }
        }

        public void addAtTail(int val) {
            if (tail == null) {
                addAtHead(val);
            } else {
                Node node = new Node(val);
                tail.next = node;
                tail = node;
            }
        }

        public void addAtIndex(int index, int val) {
            if (index < 0) {
                addAtHead(val);
                return;
            }
            // 获取index的前一个节点
            Node preNode = getNodeByIdxFromHead(index - 1);
            // index 无效
            if (preNode == null) return;
            if (preNode.next == null) {
                addAtTail(val);
                return;
            }
            Node next = preNode.next;
            Node node = new Node(val);
            preNode.next = node;
            node.next = next;
        }

        public void deleteAtIndex(int index) {
            if (index < 0) return;
            // 获取index的前一个节点
            Node preNode = getNodeByIdxFromHead(index - 1);
            // index 无效
            if (preNode == null || preNode.next == null) return;
            preNode.next = preNode.next.next;
        }

        class Node {
            public int val;
            public Node next;
            public Node(int val) {
                this.val = val;
            }

            public void list() {
                Node tmp = this;
                while (tmp != null) {
                    System.out.println(tmp.val);
                    tmp = tmp.next;
                }
            }

            @Override
            public String toString() {
                return this.val + "";
            }
        }

        /**
         * -1 0 1 2 3 4 5
         * @param index 3
         * @return 3
         */
        public Node getNodeByIdxFromHead(int index) {
            Node tmp = head;
            while (tmp != null && index >= 0) {
                tmp = tmp.next;
                index--;
            }
            return index < 0 ? tmp : null;
        }

    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */
